SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Complement (complexity)</title>

</head>

Complement (complexity)

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">In <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a>, the complement of a <a href="Decision_problem" title="Decision problem">decision problem</a> is the decision problem resulting from reversing the yes and no answers.<a href="#cite_note-1">[1]</a> Equivalently, if we define decision problems as sets of finite strings, then the <a href="Complement_(set_theory)" title="Complement (set theory)">complement</a> of this set over some fixed domain is its complement problem.<a href="#cite_note-2">[2]</a>

For example, one important problem is whether a number is a <a href="Prime_number" title="Prime number">prime number</a>. Its complement is to determine whether a number is a <a href="Composite_number" title="Composite number">composite number</a> (a number which is not prime). Here the domain of the complement is the set of all integers exceeding one.<a href="#cite_note-3">[3]</a>

There is a <a href="Turing_reduction" title="Turing reduction">Turing reduction</a> from every problem to its complement problem.<a href="#cite_note-4">[4]</a> The complement operation is an <a href="Involution_(mathematics)" title="Involution (mathematics)">involution</a>, meaning it "undoes itself", or the complement of the complement is the original problem.

One can generalize this to the complement of a <a href="Complexity_class" title="Complexity class">complexity class</a>, called the complement class, which is the set of complements of every problem in the class.<a href="#cite_note-5">[5]</a> If a class is called C, its complement is conventionally labelled co-C. Notice that this is not the complement of the complexity class itself as a set of problems, which would contain a great deal more problems.

A class is said to be closed under complement if the complement of any problem in the class is still in the class.<a href="#cite_note-6">[6]</a> Because there are Turing reductions from every problem to its complement, any class which is closed under Turing reductions is closed under complement. Any class which is closed under complement is equal to its complement class. However, under <a href="Many-one_reduction" title="Many-one reduction">many-one reductions</a>, many important classes, especially <a href="NP_(complexity)" title="NP (complexity)">NP</a>, are believed to be distinct from their complement classes (although this has not been proven).<a href="#cite_note-7">[7]</a>

The <a href="Closure_(mathematics)" title="Closure (mathematics)">closure</a> of any complexity class under Turing reductions is a superset of that class which is closed under complement. The closure under complement is the smallest such class. If a class is intersected with its complement, we obtain a (possibly empty) subset which is closed under complement.

Every deterministic complexity class (DSPACE(f(n)), DTIME(f(n)) for all f(n)) is closed under complement,<a href="#cite_note-8">[8]</a> because one can simply add a last step to the algorithm which reverses the answer. This doesn't work for nondeterministic complexity classes, because if there exist both computation paths which accept and paths which reject, and all the paths reverse their answer, there will still be paths which accept and paths which reject — consequently, the machine accepts in both cases.

Similarly, probabilistic classes such as <a href="BPP_(complexity)" title="BPP (complexity)">BPP</a>, <a href="ZPP_(complexity)" title="ZPP (complexity)">ZPP</a>, <a href="BQP" title="BQP">BQP</a> or <a href="PP_(complexity)" title="PP (complexity)">PP</a> which are defined symmetrically with regards to their yes and no instances are closed under complement. In contrast, classes such as <a href="RP_(complexity)" title="RP (complexity)">RP</a> and co-RP define their probabilities with one-sided error, and so are not (currently known to be) closed under complement.

Some of the most surprising complexity results shown to date showed that the complexity classes <a href="NL_(complexity)" title="NL (complexity)">NL</a> and <a href="SL_(complexity)" title="SL (complexity)">SL</a> are in fact closed under complement, whereas before it was widely believed they were not (see <a href="Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem" title="Immerman–Szelepcsényi theorem">Immerman–Szelepcsényi theorem</a>). The latter has become less surprising now that we know SL equals <a href="L_(complexity)" title="L (complexity)">L</a>, which is a deterministic class.

Every class which is <a href="Low_(complexity)" title="Low (complexity)">low</a> for itself is closed under complement.

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFItô1993" class="citation cs2">Itô, Kiyosi (1993), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=WHjO9K6xEm4C&pg=PA269">Encyclopedic Dictionary of Mathematics, Volume 1</a>, MIT Press, p. 269, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780262590204</bdi></cite>.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFSchrijver1998" class="citation cs2">Schrijver, Alexander (1998), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=zEzW5mhppB8C&pg=PA19">Theory of Linear and Integer Programming</a>, Wiley Series in Discrete Mathematics & Optimization, John Wiley & Sons, p. 19, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780471982326</bdi></cite>.

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFHomerSelman2011" class="citation cs2">Homer, Steven; <a href="Alan_Selman" title="Alan Selman">Selman, Alan L.</a> (2011), Computability and Complexity Theory, Texts in Computer Science, Springer, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781461406815</bdi></cite>.

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFSingh2009" class="citation cs2">Singh, Arindama (2009), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=gqWMGR1otqoC&pg=PA287">Elements of Computation Theory</a>, Texts in Computer Science, Springer, Exercise 9.10, p. 287, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781848824973</bdi></cite>.

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFBovetCrescenzi1994" class="citation cs2">Bovet, Daniele; Crescenzi, Pierluigi (1994), Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, Prentice Hall, pp. 133–134, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780139153808</bdi></cite>.

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFVollmer1999" class="citation cs2">Vollmer, Heribert (1999), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=55ZTgOJs8bsC&pg=PA113">Introduction to Circuit Complexity: A Uniform Approach</a>, Texts in Theoretical Computer Science. An EATCS Series, Springer, p. 113, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783540643104</bdi></cite>.

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFPruimWegener2005" class="citation cs2">Pruim, R.; Wegener, Ingo (2005), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=LXPVrcsdAyYC&pg=PA66">Complexity Theory: Exploring the Limits of Efficient Algorithms</a>, Springer, p. 66, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783540274773</bdi></cite>.

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFAusiello1999" class="citation cs2">Ausiello, Giorgio (1999), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=Yxxw90d9AuMC&pg=PA189">Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties</a>, Springer, p. 189, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783540654315</bdi></cite>.

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2022-10-13" href="https://en.wikipedia.org/wiki/?title=Complement_(complexity)&oldid=1115887219">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>